package 图;

import java.util.*;

/**
 * 133. 克隆图
 * 给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
 *
 * 解题思路：
 *  要克隆一个无向连通图，核心在于遍历原图的所有节点，
 *  并为每个节点创建对应的新节点，同时正确处理邻居关系。可以通过深度优先搜索（DFS）或广度优先搜索（BFS）实现。关键点如下：
 *      1、维护映射关系：使用哈希表保存原节点到克隆节点的映射，避免重复创建和循环引用。
 *      2、遍历图结构：遍历原图的所有节点，递归或迭代克隆每个节点及其邻居。
 *时间复杂度：O(N + E)，其中 N 为节点数，E 为边数。
 * 空间复杂度：O(N)，哈希表和递归栈（或队列）的空间。
 *
 * 可以优先采用DFS的思路实现
 */
public class L_133 {
    // 定义一个哈希表，用于存储已经访问过的节点和克隆后的节点的对应关系，避免重复克隆
    private HashMap<Node,Node> visited = new HashMap<>();

    /**
     * 采用DFS的思路实现
     * 递归克隆：从输入节点开始，递归克隆每个节点及其邻居。
     * 哈希表去重：使用 visited 哈希表记录已克隆的节点，避免重复克隆和循环引用。
     * @param node
     * @return
     */
    public Node cloneGraph(Node node) {
        if (node == null){
            return null;
        }
        // 如果当前节点已经克隆过，返回克隆后的节点
        if(visited.containsKey(node)){
            return visited.get(node);
        }
        // 创建新节点并记录映射关系
        Node cloneNode = new Node(node.val,new ArrayList<>());
        visited.put(node,cloneNode);

        // 递归克隆该节点的所有邻居
        for (Node neighbor: node.neighbors){
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        // 返回克隆后的节点
        return cloneNode;
    }

    /**
     * 采用BFS的思路实现
     * 队列遍历：使用队列按层遍历原图的所有节点。
     * 克隆与映射：每次遇到未克隆的邻居节点时，克隆并加入队列，确保所有节点被处理。
     * 维护邻居关系：克隆节点的邻居列表直接引用已克隆的邻居节点。
     * @param node
     * @return
     */
    public Node cloneGraphBFS(Node node) {
        if (node == null) return null;

        HashMap<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        // 克隆初始节点并入队
        Node cloneRoot = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneRoot);
        queue.offer(node);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            // 处理当前节点的所有邻居
            for (Node neighbor : curr.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // 克隆邻居节点并记录映射关系
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    queue.offer(neighbor);
                }
                // 将克隆后的邻居添加到当前克隆节点的邻居列表
                visited.get(curr).neighbors.add(visited.get(neighbor));
            }
        }

        return cloneRoot;
    }

    class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}
